'''
Created on Mar 18, 2012

@author: phuongdongbk
'''

list1 = [1,2,3,4]
def permutation(list1):
    
    if len(list1)==0 or len(list1)==1:
        return [list1]
    else:
        lenlist = len(list1) # return 4
        lastItem = list1[-1] # return 4
        lastList = list1[0:-1] # return [1,2,3]
        resultLastList = permutation(lastList) # return [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
        result = []
        for tmp in resultLastList:
            for j in range(0,lenlist):
                tmp1= list(tmp)
                tmp1.insert(j,lastItem) # return [4,1,2,3]
                result.append(tmp1)
        return result
        
print permutation(list1)
